#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};
struct TreeNode* PreorderCreate(int* a,int* i)
{
    if (a[*i] == 0)
    {
        (*i)++;
        return NULL;
    }
        
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = a[*i];
    (*i)++;
    root->left = PreorderCreate(a, i);
    root->right = PreorderCreate(a, i);
    return root;
}
//int TreeCount(struct TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    return TreeCount(root->left) + TreeCount(root->right) + 1;
//
//}
//void preorder(struct TreeNode* root, int* res, int* ressize)
//{
//    if (root == NULL)
//        return;
//    res[(*ressize)++] = root->val;
//    preorder(root->left, res, ressize);
//    preorder(root->right, res, ressize);
//}
//int* preorderTraversal(struct TreeNode* root, int* returnSize)
//{
//    int size = TreeCount(root);
//  
//    int* res = (int*)malloc(sizeof(int) * size);
//    *returnSize = 0;
//    preorder(root, res, returnSize);
//    return res;
//}
int TreeCount(struct TreeNode* root)
{
    if (!root)
        return 0;
    return TreeCount(root->left) + TreeCount(root->right) + 1;
}
void PostOrder(struct TreeNode* root, int* res, int* ressize)
{
    if (root == NULL)
        return;
    PostOrder(root->left, res, ressize);
    PostOrder(root->right, res, ressize);
    res[(*ressize)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    int size = TreeCount(root);
    int* res = (int*)malloc(sizeof(int) * size);
    *returnSize = 0;
    PostOrder(root, res, returnSize);
    return res;
}
int main()
{
    int arr[19] = { 1,2,4,0,0,5,8,0,0,0,3,6,0,9,0,0,7,0,0,};
    struct TreeNode* root = NULL;
    int n = 0;
    root = PreorderCreate(arr,&n);
    int* arr2= postorderTraversal(root, &n);
    int size = TreeCount(root);
    for (int i = 0; i < size; i++)
        printf("%d  ", arr2[i]);
   
    return 0;
}